package com.itheima.algorithm.dynamicprogramming;

import java.util.Arrays;

/*
卡特兰数
 */
public class Catalan {
    public static void main(String[] args) {
        System.out.println(catalan(5));
    }

    static int catalan(int n){
        // 从C（0）开始计算的
        int [] dp = new int[n + 1];
        dp[0] = 1; // C(0) = 1
        dp[1] = 1; // C(1) = 1
        for(int j = 2;j<=n;j++){
            for(int i = 0;i < j; i++){ // 第j个卡特兰数的计算
                System.out.printf("(%d,%d)\t",i,j-1-i);
                dp[j] += dp[i] * dp[j-i-1];
            }
            System.out.println();
            System.out.println(Arrays.toString(dp));
        }
        return dp[n];
    }
}
